package mo.leetcode_top;

import java.util.Random;

public class L528_2 {

    private Random random = new Random();
    private int[] preSum;
    private int length;
    private int sum;

    public L528_2(int[] w) {
        length = w.length;
        preSum = new int[length];
        preSum[0] = w[0];
        sum = w[0];
        for (int i = 1; i < length; i++) {
            preSum[i] += preSum[i-1] + w[i];
            sum += w[i];
        }
    }

    public int pickIndex() {
        int value = random.nextInt(sum) + 1;
        int left = 0;
        int right = length - 1;
        while (left < right) {
            int mid = (left + right) >>> 1;
            if (preSum[mid] < value) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        L528_2 test = new L528_2(new int[]{1, 3, 1});
        for (int i = 0; i < 10; i++) {
            System.out.println(test.pickIndex());
        }
    }

}
